二叉树的比较

function Node (value) {
    this.value = value;
    this.left = null;
    this.right = null;
}

const a1 = new Node('a');
const b1 = new Node('b');
const c1 = new Node('c');
const d1 = new Node('d');
const e1 = new Node('e');

a1.left = b1;
a1.right = c1;
b1.left = d1;
b1.right = e1;

const a2 = new Node('a');
const b2 = new Node('b');
const c2 = new Node('c');
const d2 = new Node('d');
const e2 = new Node('e');

a2.left = b2;
a2.right = c2;
b2.left = d2;
b2.right = e2;

左右子树不可互换（完全相等）

function compareTree (root1, root2) {
    if (root1 == root2) return true;
    if (root1 == null && root2 != null || root2 == null && root1 != null) return false;
    if (root1.value != root2.value) return false;  // 相同位置的值不相等
    const leftBool = compareTree(root1.left, root2.left);  // 递归对左子树进行判断
    const rightBool = compareTree(root1.right, root2.right);  // 递归对右子树进行判断
    return leftBool && rightBool;  // 必须左右子树都相等才算相等
}
console.log(compareTree(a1, a2));  //--> true

左右子树可以互换

function compareTree (root1, root2) {
    if (root1 == root2) return true;
    if (root1 == null && root2 != null || root2 == null && root1 != null) return false;
    if (root1.value != root2.value) return false;  // 相同位置的值不相等
    return compareTree(root1.left, root2.left) && compareTree(root1.right, root2.right)
        || compareTree(root1.left, root2.right) && compareTree(root1.right, root2.left);
}
console.log(compareTree(a1, a2));  //--> true

diff 算法

function diffTrue (root1, root2, diffList = []) {
    if (root1 == root2) return diffList;
    if (root1 == null && root2 != null) {  // 新增
        diffList.push({ type: '新增', origin: null, now: root2 });
    } else if (root1 != null && root2 == null) {
        diffList.push({ type: '删除', origin: root1, now: null });
    } else if (root1.value != root2.value) {
        diffList.push({ type: '修改', origin: root1, now: root2 });
    } else {
        diffTrue(root1.left, root2.left, diffList);
        diffTrue(root1.right, root2.right, diffList);
    }
    return diffList;
}
console.log(diffTrue(a1, a2));  //--> []